package 纯数组;

import com.alibaba.fastjson.JSON;
import javafx.util.Pair;

import java.util.*;

public class No310最小高度树 {

    /**
     * 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
     * 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
     * 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
     * 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
     * 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
     *  
     *
     * 示例 1：
     * 输入：n = 4, edges = [[1,0],[1,2],[1,3]]
     * 输出：[1]
     * 解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
     * 示例 2：
     * 输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
     * 输出：[3,4]
     * 示例 3：
     * 输入：n = 1, edges = []
     * 输出：[0]
     * 示例 4：
     * 输入：n = 2, edges = [[0,1]]
     * 输出：[0,1]
     *  
     * 提示：
     * 1 <= n <= 2 * 104
     * edges.length == n - 1
     * 0 <= ai, bi < n
     * ai != bi
     * 所有 (ai, bi) 互不相同
     * 给定的输入 保证 是一棵树，并且 不会有重复的边
     */

    /**
     * 比较容易想到的超时解法; normal->超时;
     * 下方有GOOD解法
     */
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        List<Integer> result=new ArrayList<>();

        if(edges.length==0&&n!=0){
            result.add(0);
            return result;
        }

        if(edges.length == 0){
            return result;
        }

        //当前index元素 指向 [...] 哪些元素
        List<List<Integer>> lists=new ArrayList<>();

        int maxDeep=Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            lists.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            lists.get(edge[0]).add(edge[1]);
            lists.get(edge[1]).add(edge[0]);
        }

        //从0..(n-1)开始遍历高度
        for (int i = 0; i < n; i++) {
            //表示当前已用的元素
            HashSet<Integer> set=new HashSet<>();
            set.add(i);
            //当前指向的元素
            List<Integer> list = lists.get(i);
            //迭代队列  (当前元素+当前深度)
            Deque<Pair<Integer,Integer>> queue=new ArrayDeque<>();

            for (Integer integer : list) {
                queue.addLast(new Pair<>(integer,1));
                set.add(integer);
            }

            int currentMaxDeep=0;

            //开始广度搜索
            while (!queue.isEmpty()){

                Pair<Integer, Integer> pair = queue.pollFirst();

                Integer num = pair.getKey();
                Integer deep = pair.getValue();

                for (Integer integer : lists.get(num)) {
                    if(!set.contains(integer)){
                        //不包含,则可以放入
                        queue.addLast(new Pair<>(integer,deep+1));
                        set.add(integer);
                    }
                }

                currentMaxDeep=Math.max(currentMaxDeep,deep);

            }

            if(currentMaxDeep==maxDeep){
                //当前正好
                result.add(i);
            }else if(currentMaxDeep<maxDeep){
                result.clear();
                result.add(i);
                maxDeep=currentMaxDeep;
            }

        }

        return result;

    }

    /**
     * 参考wei wei哥: https://leetcode-cn.com/problems/minimum-height-trees/solution/tan-xin-fa-gen-ju-tuo-bu-pai-xu-de-si-lu-python-da/
     * 贪心思想: 度最小的节点必定是边缘节点,就慢慢剔除边缘节点,只剩下一个节点或者两个节点时就是答案。
     * 度(一个节点的连接数)
     */
    public List<Integer> findMinHeightTreesGood(int n, int[][] edges) {

        List<Integer> result=new ArrayList<>();

        if (n <= 2) {
            for (int i = 0; i < n; i++) {
                result.add(i);
            }
            return result;
        }

        int sourceN=n;

        int[] arr=new int[n];
        List<List<Integer>> lists=new ArrayList<>();

        for (int i = 0; i < n; i++) {
            lists.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            arr[edge[0]]++;
            arr[edge[1]]++;
            lists.get(edge[0]).add(edge[1]);
            lists.get(edge[1]).add(edge[0]);
        }

        Deque<Integer> queue=new ArrayDeque<>();
        Set<Integer> isExitSet=new HashSet<>();

        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==1){
                //只有一个指向
                queue.addLast(i);
                isExitSet.add(i);
            }
        }

        //减到只剩下1~2个节点位为止
        while (n>2){

            int size=queue.size();
            n-=size;

            for (int i = 0; i < size; i++) {

                Integer removeFirstNum = queue.removeFirst();
                //退出当前树
                isExitSet.add(removeFirstNum);
                for (Integer integer : lists.get(removeFirstNum)) {
                    arr[integer]--;
                    if(arr[integer]==1){
                        queue.addLast(integer);
                    }
                }

            }

        }

        for (int i = 0; i < sourceN; i++) {
            if(!isExitSet.contains(i)){
                result.add(i);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        No310最小高度树 n=new No310最小高度树();
        int[][] arr={{0,1},{0,2},{0,3},{3,4},{4,5}};
        List<Integer> result = n.findMinHeightTreesGood(6, arr);
        System.out.println(JSON.toJSONString(result));

    }

}
